Packet switching arrangements have proven to be preferred switching networks for many types of digital communication. Data packets, each comprising a data portion and a numerical designation of network output port are applied to the input of such a network and the network conveys each packet to the designated output port.
One common packet network is called an expansion network and comprises a plurality of interconnected switch elements having two inputs and two outputs. Switch elements receive packets at both inputs, interpret the output port designations and connect the input packets to the switch element outputs. When two packets enter a switch element destined for the same switch element output, one packet is blocked since only one packet can be sent to a single output at a time. Packet blocking reduces the packet transmission rate of expansion networks and requires facilities for the recovery of the blocked of packets. One expansion network called an Omega network is described in "Access and Alignment of Data in an Array Processor," Transaction Computers, Vol. C-24, No. 12, December, 1975, pp. 1145-1155.
A packet switching network described by Huang and Knauer in "STARLITE: A Wideband Digital Switch," Globecom 1984, pp. 121-124 avoids the blocking problem of expansion networks by sorting incoming packets into ascending (or descending) order based on their destination before they are applied to the inputs of the expansion network. The presorting of packets removes the combinations of input packets which would result in blocking. Since blocking is avoided, the throughput of the network is improved and additional complexities to recover blocked packets are unnecessary. The blocking reduction achieved by the "sort-then-expand" network described by Huang et al. is a great advantage in packet switching. However, difficulties occur in the fabrication of such networks which include large numbers of input and output ports.
To switch groups of packets in a sort-then-expand network the switch elements of both the sort and the expand stages must be fully interconnected so that a packet at any input position within the group can be connected to any output position of the group. Known sort-then-expand networks, such as the Huang et al. network, sort all received packets as a single group and expand the sorted sequence as a single group. Such networks must include full interconnectivity which is achieved by providing multiple layers of switch elements and complex connections between the layers. When the number of packets in the group is the size required for a commercial product, e.g., 128 or more, many layers of switch elements are required resulting in large amounts of switching circuitry with complex interconnections.
The number of circuit packs required to fabricate a design is determined in part by the amount of circuitry on a circuit pack which is limited by power, heat dissipation and surface area available as well as by the number of input and output connections required by the circuitry on the circuit pack. When standard circuit layout techniques are applied to known commercial size sort-then-expand networks, the number of circuit packs required is large because of: (a) the large amount of switching circuitry required (many layers) and (b) the full interconnectivity of the circuitry decreases the amount of circuitry which can be placed on each circuit pack as a result of input/output connection limitations. This large number of circuit packs results in fabricated products which are large, complex and costly.
In view of the foregoing, a need exists in the art for a commercial size packet switch network which provides the advantageous characteristics of a sort-then-expand network without the size, complexity and cost problems of known systems.